#include <bits/stdc++.h>
using namespace std;

/*
1513. 仅含 1 的子串数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

 

示例 1：

输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次
示例 2：

输入：s = "101"
输出：2
解释：子字符串 "1" 在 s 中共出现 2 次
示例 3：

输入：s = "111111"
输出：21
解释：每个子字符串都仅由 '1' 组成
示例 4：

输入：s = "000"
输出：0
 

提示：

s[i] == '0' 或 s[i] == '1'
1 <= s.length <= 10^5
*/

// 法一
class Solution {
public:
    using ll = long long;
    int numSub(string s) {
        const int MOD = 1e9 + 7;
        int ans = 0;
        int curLen = 0;
        for (char c : s) {
            if (c == '1')   curLen++;
            else {
                // arrive 0 cal cur 连续1的子串数（k*(k+1)/2） sum to ans
                ans = (ans + (ll)curLen * (curLen + 1) / 2) % MOD;
                curLen = 0;
            }
        }
        // str end all1
        ans = (ans + (ll)curLen * (curLen + 1) / 2) % MOD;
        return ans;
    }
};

// 法二
class Solution {
public:
    int numSub(string s) {
        uint32_t ans = 0;                  // 累计全1子串数（用uint32_t减少溢出风险）
        constexpr long long MOD = 1e9 + 7; // 取模常量
        long long late_zire = -1;          // 记录上一个'0'的位置（初始-1：字符串起始前无0）

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '0')    late_zire = i; // 遇到0，更新上一个0的位置
            else                ans += i - late_zire;   // 遇到1：新增子串数 = 当前1到上一个0之间的长度（i - late_zire）
        }
        return ans % MOD; // 结果取模，避免溢出
    }
};